//
//  compare_chars.hpp
//  cpp_algorithm
//
//  Created by 李贺 on 2021/12/8.
//

#ifndef compare_chars_hpp
#define compare_chars_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
#include <string>
using namespace std;

class Solution_compare_chars {

public:
    vector<string> commonChars(vector<string>& A) {
            vector<string> result;
            if (A.size() == 0) return result;
            int hash[26] = {0}; // 用来统计所有字符串里字符出现的最小频率
            for (int i = 0; i < A[0].size(); i++) { // 用第一个字符串给hash初始化
                char temp = A[0][i];
                int index = temp - 'a';
                hash[index] = hash[index] + 1;
            }

            int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
            for (int i = 1; i < A.size(); i++) {
                memset(hashOtherStr, 0, 26 * sizeof(int));
                for (int j = 0; j < A[i].size(); j++) {
                    char temp = A[i][j];
                    int index = temp - 'a';
                    int count = hashOtherStr[index];
                    hashOtherStr[index] = count + 1;
                }
                // 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
                for (int k = 0; k < 26; k++) {
                    hash[k] = min(hash[k], hashOtherStr[k]);
                }
            }
            // 将hash统计的字符次数，转成输出形式
            for (int i = 0; i < 26; i++) {
                while (hash[i] != 0) { // 注意这里是while，多个重复的字符
                    string s(1, i + 'a'); // char -> string
                    result.push_back(s);
                    hash[i]--;
                }
            }

            return result;
    }
    
    void test() {
        vector<string> arr = vector<string>();
        arr.push_back("cool");
        arr.push_back("lock");
        arr.push_back("cook");
        
        vector<string> res = commonChars(arr);
        for (int i = 0; i < res.size(); i++) {
            cout << res.at(i) << "\n";
        }
    }
    
};

#endif /* compare_chars_hpp */
